package leetcode.editor.vscdev.hot100;

import java.util.*;

/* 请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。 */
public class lc146 {

}

class LRUCache1013 {
    // 双向链表
    private static class Node {
        Node prev;
        Node next;
        int key, val;

        Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    // map缓存 键为链表键
    HashMap<Integer, Node> map = new HashMap<>();
    int capacity = 0;
    Node dummy = new Node(0, 0);

    public LRUCache1013(int capacity) {
        this.capacity = capacity;
        dummy.prev = dummy;
        dummy.next = dummy;
    }

    int get(int key) {
        // 通过key从map获取node
        Node node = map.getOrDefault(key, null);
        if (node == null) {
            return -1;
        }
        remove(node);
        insertNodeHead(node);
        return node.val;
    }

    void put(int key, int value) {
        // 判断是否有
        boolean hasNode = get(key) == -1 ? false : true;
        if (hasNode) {
            // 有则更新, Node及map
            Node node = map.get(key);
            node.val = value;
        } else {
            // 无则头插进入链表写入map
            Node node = new Node(key, value);
            insertNodeHead(node);
            map.put(key, node);
        }
        if (map.size() > capacity) {
            // 若超出容量, 除去末尾元素
            map.remove(dummy.prev.key);
            remove(dummy.prev);
        }
    }

    void remove(Node node) {
        node.next.prev = node.prev;
        node.prev.next = node.next;
        node.next = null;
        node.prev = null;
    }

    void insertNodeHead(Node node) {
        node.next = dummy.next;
        dummy.next = node;
        node.next.prev = node;
        node.prev = dummy;
    }
}

class LRUCacheOld {
    // 尝试HashMap + 自己构建双向链表
    private static class Node {

        Node pre, next;
        int key, value;

        Node(int k, int v) {
            key = k;
            value = v;
        }
    }

    private final int capacity;
    // 哨兵节点，类似于头结点的一个逻辑，不过这个链表是成环的，dummy的前一个节点就是尾结点。
    private final Node dummy = new Node(0, 0);
    private final Map<Integer, Node> keyToNode = new HashMap<>();

    public LRUCacheOld(int capacity) {
        this.capacity = capacity;
        dummy.pre = dummy;
        dummy.next = dummy;
    }

    public int get(int key) {
        Node node = getNode(key);
        return node == null ? -1 : node.value;
    }

    public void put(int key, int value) {
        // put也有读操作
        Node node = getNode(key);
        if (node != null) { // 有这key
            node.value = value; // 更新 value
            return;
        }
        node = new Node(key, value); // 新key
        keyToNode.put(key, node);
        pushFront(node); // 放到最上面
        if (keyToNode.size() > capacity) { // key太多了
            Node backNode = dummy.pre;
            keyToNode.remove(backNode.key);
            remove(backNode); // 去掉最后的key
        }
    }

    // 获取 key 对应的节点，同时把该节点移到链表头部
    private Node getNode(int key) {
        if (!keyToNode.containsKey(key)) { // 没有该key
            return null;
        }
        Node node = keyToNode.get(key); // 有这个key
        remove(node); // 删除这个Node
        pushFront(node); // 放到最上面
        return node;
    }

    // 删除该Node
    private void remove(Node node) {
        // 让当前node失去链接，并使其前后节点相连
        node.next.pre = node.pre;
        node.pre.next = node.next;
    }

    // 放到链表头部
    private void pushFront(Node node) {
        node.next = dummy.next;
        node.pre = dummy;
        node.next.pre = node.pre;
        node.pre.next = node.next;
    }
}

class LRUCacheEasy {

    private int capacity;
    private LinkedHashMap<Integer, Integer> map;
    // LinkedHashMap的有序可以按照两种顺序排序，1.插入顺序 2.读取顺序
    // 读取顺序由三个回调函数维护
    // 1.afterNodeAccess 访问元素后将该元素放到双向链表尾部
    // 2.afterNodeRemoval 在删除元素后，将元素从双向链表删除
    // 3.afterNodeInsertion 插入元素后，判断是否需要移除一直不用的一些元素

    public LRUCacheEasy(int capacity) {
        this.capacity = capacity;
        // 使用 access-order 模式（true），并在超过容量时自动移除最老条目
        this.map = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(java.util.Map.Entry<Integer, Integer> eldest) {
                return size() > LRUCacheEasy.this.capacity;
            }
        };
    }

    public int get(int key) {
        // if (map.containsKey(key)){
        // return map.get(key);
        // }
        // return -1;
        return map.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        map.put(key, value);
    }
}
/*
 * 
 * // 插入新节点才会触发该方法，因为只有插入新节点才需要内存
 * // 根据 HashMap 的 putVal 方法, evict 一直是 true
 * // removeEldestEntry 方法表示移除规则, 在 LinkedHashMap 里一直返回 false
 * // 所以在 LinkedHashMap 里这个方法相当于什么都不做
 * 
 * void afterNodeInsertion(boolean evict) { // possibly remove eldest
 * LinkedHashMap.Entry<K,V> first;
 * // 根据条件判断是否移除最近最少被访问的节点
 * if (evict && (first = head) != null && removeEldestEntry(first)) {
 * K key = first.key;
 * removeNode(hash(key), key, null, false, true);
 * }
 * }
 * 
 * // 移除最近最少被访问条件之一，通过覆盖此方法可实现不同策略的缓存
 * // LinkedHashMap是默认返回false的，我们可以继承LinkedHashMap然后复写该方法即可
 * // 例如 LeetCode 第 146 题就是采用该种方法，直接 return size() > capacity;
 * protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
 * return false;
 * }
 */

/**
 * 1. 使用 get 方法会访问到节点, 从而触发调用这个方法 2. 使用 put 方法插入节点, 如果 key 存在, 也算要访问节点, 从而触发该方法
 * 3. 只有 accessOrder 是 true 才会调用该方法 4. 这个方法会把访问到的最后节点重新插入到双向链表结尾
 */
/*
 * void afterNodeAccess(Node<K,V> e) { // move node to last
 * // 用 last 表示插入 e 前的尾节点
 * // 插入 e 后 e 是尾节点, 所以也是表示 e 的前一个节点
 * LinkedHashMap.Entry<K,V> last;
 * //如果是访问序，且当前节点并不是尾节点
 * //将该节点置为双向链表的尾部
 * if (accessOrder && (last = tail) != e) {
 * // p: 当前节点
 * // b: 前一个节点
 * // a: 后一个节点
 * // 结构为: b <=> p <=> a
 * LinkedHashMap.Entry<K,V> p =
 * (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
 * // 结构变成: b <=> p <- a
 * p.after = null;
 * 
 * // 如果当前节点 p 本身是头节点, 那么头结点要改成 a
 * if (b == null)
 * head = a;
 * // 如果 p 不是头尾节点, 把前后节点连接, 变成: b -> a
 * else
 * b.after = a;
 * 
 * // a 非空, 和 b 连接, 变成: b <- a
 * if (a != null)
 * a.before = b;
 * // 如果 a 为空, 说明 p 是尾节点, b 就是它的前一个节点, 符合 last 的定义
 * // 这个 else 没有意义，因为最开头if已经确保了p不是尾结点了，自然after不会是null
 * else
 * last = b;
 * 
 * // 如果这是空链表, p 改成头结点
 * if (last == null)
 * head = p;
 * // 否则把 p 插入到链表尾部
 * else {
 * p.before = last;
 * last.after = p;
 * }
 * tail = p;
 * ++modCount;
 * }
 * }
 */
